package com.cqs.leetcode.link;

import com.cqs.leetcode.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author lixw
 * @date 2020/2/29 9:01
 */
public class LinkedListCycle141 {

    /***
     * 有环的话 遍历链表结束前结点会重复出现
     * 时间复杂度 O(N)
     * 空间复杂度 O(N)
     */
    static public class Solution {
        public boolean hasCycle(ListNode head) {
            Set<ListNode> exists = new HashSet<>();
            while (head != null) {
                if (exists.contains(head)) return true;
                exists.add(head);
                head = head.next;
            }
            return false;
        }
    }

    /**
     * 快慢指针
     * <p>
     * 时间复杂度O(n) 最多走两边的
     * 若存在环：当快慢指针都走到环里面，那么快指针-> 慢指针的位置相差k个结点(k < n)
     * 因为每次快指针多走一步，既可以缩短一个结点的距离，所以只要k次就可以追上慢指针
     */
    static public class Solution2 {
        public boolean hasCycle(ListNode head) {
            //初始化
            if (head == null || head.next == null) return false;
            ListNode slow = head, fast = head.next;
            //无环的话，fast会率先变成null
            while (fast != null) { //（无环结束条件）
                //注意(有环)循环结束条件
                if (fast == slow) return true;
                slow = slow.next;
                fast = fast.next;
                //注意空指针
                if (fast != null) {
                    fast = fast.next;
                }
            }
            return false;
        }
    }
}
